#include <malloc.h>
#include "stdio.h"

/**
 * 设单链表的表头指针为h，节点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n)，判断该链表的前n个字符是否中心对称
 */

typedef struct LinkList {
    char data;
    struct LinkList *next;
} LinkList;

/**
 * 定义算法，返回0表示错误，1表示正确
 * @param head
 * @param n
 * @return
 */
int dc(LinkList *head, int n) {
    int n2 = n / 2;
    char *datas = (char *) malloc(sizeof(char) * n2);
    for (int i = 0; i < n2; ++i) {
        datas[i] = head->data;
        head = head->next;
    }
    if (n % 2 == 1) {
        head = head->next;
    }
    for (int i = n2 - 1; i > -1; i--) {
        if (head->data == datas[i]) {
            head = head->next;
        } else {
            return 0;
        }
    }
    return 1;
}

LinkList *createNode(char data) {
    LinkList *node = (LinkList *) malloc(sizeof(LinkList));
    node->data = data;
    node->next = NULL;
    return node;
}

void freeLinkList(LinkList *head) {
    LinkList *next = head->next;
    free(head);
    while (next != NULL) {
        LinkList *now = next;
        free(now);
        next = next->next;
    }
}

void printLinkList(LinkList *head) {
    int count = 0;
    printf("printLinkList:");
    while (head != NULL) {
        printf("%c", head->data);
        head = head->next;
        count++;
    }
    printf("\nlist length: %d\n", count);
}

int main() {
    // 定义一组传入数据用于创建链表
    char data[] = "abbabbccc";
    // 传入算法的n
    int  n = 4;
    int length = sizeof(data) / sizeof(data[0]);
    // 创建一个头结点
    LinkList *head = createNode(data[0]);
    LinkList *pList = head;
    // 不断创建下一个结点
    for (int i = 1; i < length - 1; ++i) {
        char item = data[i];
        pList->next = createNode(item);
        pList = pList->next;
    }
    printLinkList(head);
    printf("%d", dc(head, n));
    freeLinkList(head);
    return 0;
}